#include <inttypes.h>

#include <iostream>
#include <map>
#include <string>
using std::cout;
using std::endl;

// 递归就是假设子问题已知，利用子问题求解。一般是倒着来，嵌套调用，直到第一步才return
// 递推公式模板：f(n) = f(n-k) + x
// 退出条件模板：if(n==1) return y;

// 递归求电影院第几排
// f(n) = f(n-1) + 1
// f(1) = 1
int MovieHow(int n) {
  if (n == 1) return 1;
  return MovieHow(n - 1) + 1;
}
// 非递归
int MovieHow2(int n) {
  int ret = 1;
  for (int i = 1; i < n; ++i) {
    ret += 1;
  }
  return ret;
}
void TestMovieHow() {
  cout << MovieHow(1) << endl;
  cout << MovieHow(3) << endl;
  cout << MovieHow2(3) << endl;
  cout << MovieHow(100) << endl;  // 层数太多 有栈溢出风险
}

// 楼梯每次可以走1个或2个台阶。递归求一共多少种走法
// f(n) = f(n-1) + f(n-2)
// f(1) = 1
// f(2) = 2
static std::map<int, int64_t> stairCache;
int64_t StairMove(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  int64_t ret = -1;
  auto it = stairCache.find(n);
  if (it == stairCache.end()) {
    ret = StairMove(n - 1) + StairMove(n - 2);
    stairCache[n] = ret;
  } else {
    ret = it->second;
  }
  return ret;
}
void TestStairMove() {
  cout << StairMove(1) << endl;
  cout << StairMove(10) << endl;
  cout << StairMove(100) << endl;
}

static std::map<std::string, std::string> meAndRefer;
// 最终推荐人
std::string FindReferrer(const std::string& me) {
  auto it = meAndRefer.find(me);
  if (it == meAndRefer.end()) return "";

  const std::string& refer = it->second;
  if (me == refer) return me;
  return FindReferrer(refer);
}
void TestFindReferrer() {
  meAndRefer["A"] = "A";
  meAndRefer["B"] = "A";
  meAndRefer["C"] = "B";
  meAndRefer["D"] = "C";
  cout << FindReferrer("C") << endl;
  cout << FindReferrer("B") << endl;
  cout << FindReferrer("A") << endl;
}

int main() {
  TestMovieHow();
  cout << "--------\n";
  TestStairMove();
  cout << "--------\n";
  TestFindReferrer();
}